package com.zhugang.week02;

/**
 * @program algorithms
 * @description: removeElements
 * @author: chanzhugang
 * @create: 2022/04/12 08:09
 */
public class RemoveElements {

    public class ListNode {
        public int data;
        public ListNode next;

        public ListNode(int data, ListNode next) {
            this.data = data;
            this.next = next;
        }

        public ListNode() {
        }
    }

    /**
     * 移除链表中指定值的节点
     *
     * @param head
     * @param value
     * @return
     */
    public ListNode removeElements(ListNode head, int value) {
        if (head == null) {
            return null;
        }
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.data == value) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        if (head.data == value) {
            // 特殊处理 头结点也符合value
            head = head.next;
        }
        return head;
    }

    /**
     * 引入虚拟头结点
     *
     * @param head
     * @param value
     * @return
     */
    public ListNode removeElements2(ListNode head, int value) {
        if (head == null) {
            return null;
        }
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode prev = newHead;
        while (prev.next != null) {
            if (prev.next.data == value) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return newHead.next;
    }


    /**
     * 改变链表的万能写法，开辟一个新的链表
     * 重新定义一个链表，不等于指定元素的结点追加到该链表 （遍历 + 尾部插入）
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements3(ListNode head, int val) {
        // 开辟新链表，遍历满足条件尾部插入
        ListNode virtualNode = new ListNode();
        ListNode tail = virtualNode;
        ListNode p = head;
        while (p != null) {
            ListNode temp = p.next;
            if (p.data != val) {
                // 此时p是尾节点
                p.next = null;
                tail.next = p;
                tail = p;
            }
            p = temp;
        }
        return virtualNode.next;
    }
}